#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/4/22 09:25|09:25
# @Author  : yangdingyi
# @File    : 199. 二叉树的右视图.2020-04-22
# @Software: PyCharm

# Definition for a binary tree node.
from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rightSideView(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        # from queue import Queue
        # que = Queue()
        # que.put(root)
        que = [root]
        ans = [root.val]
        lq = len(que)
        while lq > 0:
            q2 = []
            lq2 = 0
            for i in range(lq):
                x = que[i]
                if x.left:
                    q2.append(x.left)
                    lq2 += 1
                if x.right:
                    q2.append(x.right)
                    lq2 += 1
            lq = lq2
            que = q2
            if lq > 0:
                ans.append(que[lq - 1].val)
        return ans


def makeTree(data):
    ld = len(data)
    if ld <= 0:
        return None
    rt = TreeNode(data[0])
    que = [rt]
    lq = 1
    qi = 0
    i = 1
    while i < ld and qi < lq:
        x = que[qi]
        if x:
            d = data[i]
            if d is not None:
                x.left = TreeNode(d)
            else:
                x.left = None
            que.append(x.left)
            lq += 1
            i += 1
            d = data[i]
            if d is not None:
                x.right = TreeNode(d)
            else:
                x.right = None
            que.append(x.right)
            lq += 1
            i += 1
        qi += 1
    return rt


def display(rt, pre=''):
    if not rt:
        print(pre, rt)
        return
    display(rt.right, pre + ' ')
    print(pre, rt.val)
    display(rt.left, pre + ' ')


solve = Solution()
tree = [1, 2, 3, None, 5, None, 4]
print(tree)
rt = makeTree(tree)
display(rt)
print(solve.rightSideView(rt))




